package cn.zifangsky.sort;

import java.util.ArrayList;
import java.util.List;

/**
 * 基数排序
 *
 * @author zifangsky
 * @date 2019/1/15
 * @since 1.0.0
 */
public class RadixSort {

    private final static int BUCKETS = 128;

    /**
     * 基数排序（使用 ArrayList 辅助）
     * <p><b>时间复杂度：</b>O(p(N + b))，其中p是趟数，N是待排序元素个数，b是桶</p>
     * <p><b>Note：</b>这个示例只能排序非负整数</p>
     * @author zifangsky
     * @date 2019/1/15 11:05
     * @since 1.0.0
     * @param array 待排序数组
     */
    public static int[] sortNum1(int[] array){
        if(array == null || array.length < 1){
            throw new IllegalArgumentException("Illegal initial array");
        }

        int length = array.length;

        //1. 定义一个多个桶组成的List，并初始化
        List<Integer>[] buckets = new ArrayList[10];
        for(int i = 0; i < 10; i++){
            buckets[i] = new ArrayList<>();
        }

        //2. 有多少位就进行多少次桶排序
        int max = findMax(array);
        for(int i = 1; (max / i) > 0; i = i * 10){
            //2.1 扫描待排序数组，然后根据当前排序的位数上的数字，将元素添加到桶中
            for(int j = 0; j < length; j++){
                int num = (array[j] / i) % 10;
                buckets[num].add(array[j]);
            }

            //2.2 每次桶排序结束后，从桶中取值
            int index = 0;
            for(List<Integer> list : buckets){
                for(Integer temp : list){
                    array[index] = temp;
                    index++;
                }

                //2.3 清空List
                list.clear();
            }
        }

        return array;
    }

    /**
     * 基数排序（不使用 ArrayList 辅助）
     * <p><b>时间复杂度：</b>O(p(N + b))，其中p是趟数，N是待排序元素个数，b是桶</p>
     * <p><b>Note：</b>这个示例只能排序非负整数</p>
     * @author zifangsky
     * @date 2019/1/15 11:05
     * @since 1.0.0
     * @param array 待排序数组
     */
    public static int[] sortNum2(int[] array){
        if(array == null || array.length < 1){
            throw new IllegalArgumentException("Illegal initial array");
        }

        int length = array.length;

        //1. 有多少位就进行多少次桶排序
        int max = findMax(array);
        for(int i = 1; (max / i) > 0; i = i * 10){
            //2. 执行桶排序，先后根据个位、十位、百位等等进行排序

            //2.1 定义一个length行，10列（因为数字只有0~9）的二维数组
            Integer[][] buckets = new Integer[length][10];

            //2.2 扫描待排序数组，然后根据当前排序的位数上的数字，将元素放入到二维数组表示的桶中
            for(int j = 0; j < length; j++){
                int num = (array[j] / i) % 10;
                buckets[j][num] = array[j];
            }

            //2.3 每次桶排序结束后，从桶中取值
            int index = 0;
            for(int n = 0; n < 10; n++){
                for(int m = 0; m < length; m++){
                    if(buckets[m][n] != null){
                        array[index] = buckets[m][n];
                        index++;
                    }
                }
            }
        }

        return array;
    }

    /**
     * 查找数组的最大值
     */
    private static int findMax(int[] array){
        int result = array[0];

        for(int temp : array){
            if(temp > result){
                result = temp;
            }
        }

        return result;
    }




    /**
     * 基数排序（使用 ArrayList 辅助排序定长字符串数组）
     * <p><b>时间复杂度：</b>O(p(N + b))，其中p是趟数，N是待排序元素个数，b是桶</p>
     * @author zifangsky
     * @date 2019/1/15 16:37
     * @since 1.0.0
     * @param array 待排序数组
     * @param strLength 字符串的长度
     */
    public static String[] sortStr1(String[] array, int strLength){
        if(array == null || array.length < 1){
            throw new IllegalArgumentException("Illegal initial array");
        }

        //1. 定义一个多个桶组成的List，并初始化
        List<String>[] buckets = new ArrayList[BUCKETS];
        for(int i = 0; i < BUCKETS; i++){
            buckets[i] = new ArrayList<>();
        }

        //2. 有多少位就进行多少次桶排序
        for(int i = strLength - 1; i >= 0; i--){
            //2.1 扫描待排序数组，然后将元素放入到桶中
            for(String temp : array){
                buckets[temp.charAt(i)].add(temp);
            }

            //2.2 每次桶排序结束后，从桶中取值
            int index = 0;
            for(List<String> list : buckets){
                for(String temp : list){
                    array[index] = temp;
                    index++;
                }

                //2.3 清空List
                list.clear();
            }
        }

        return array;
    }

    /**
     * 基数排序（不使用 ArrayList 辅助排序定长字符串数组）
     * <p><b>时间复杂度：</b>O(p(N + b))，其中p是趟数，N是待排序元素个数，b是桶</p>
     * @author zifangsky
     * @date 2019/1/15 16:48
     * @since 1.0.0
     * @param array 待排序数组
     * @param strLength 字符串的长度
     */
    public static String[] sortStr2(String[] array, int strLength){
        if(array == null || array.length < 1){
            throw new IllegalArgumentException("Illegal initial array");
        }

        int length = array.length;

        //1. 有多少位就进行多少次桶排序
        for(int i = strLength - 1; i >= 0; i--){
            //1.1 定义一个二维数组
            String[][] buckets = new String[length][BUCKETS];

            //1.2 扫描待排序数组，然后将元素放入到桶中
            for(int j = 0; j < length; j++){
                buckets[j][array[j].charAt(i)] = array[j];
            }

            //1.3 每次桶排序结束后，从桶中取值
            int index = 0;
            for(int n = 0; n < BUCKETS; n++){
                for(int m = 0; m < length; m++){
                    if(buckets[m][n] != null){
                        array[index] = buckets[m][n];
                        index++;
                    }
                }
            }
        }

        return array;
    }

    /**
     * 基数排序（使用 ArrayList 辅助排序不定长字符串数组，且以最高位为基准进行排序）
     * <p><b>时间复杂度：</b>O(p(N + b))，其中p是趟数，N是待排序元素个数，b是桶</p>
     * @author zifangsky
     * @date 2019/1/15 16:37
     * @since 1.0.0
     * @param array 待排序数组
     */
    public static String[] sortStr3(String[] array){
        if(array == null || array.length < 1){
            throw new IllegalArgumentException("Illegal initial array");
        }

        //获取数组中的字符串的最大位数
        int maxStrLen = findMaxDigit(array);
        int length = array.length;

        //1. 定义一个 length 长的数组，并初始化
        List<String>[] buckets = new ArrayList[BUCKETS];
        //2. 按照输入的字符串的不同长度，将它们分割到不同的 List 中
        List<String>[] wordsLengths = new ArrayList[maxStrLen + 1];

        for(int i = 0; i < BUCKETS; i++){
            buckets[i] = new ArrayList<>();
        }
        for(int i = 0; i < wordsLengths.length; i++){
            wordsLengths[i] = new ArrayList<>();
        }
        for(String temp : array){
            wordsLengths[temp.length()].add(temp);
        }

        //3. 重新排序原数组，将字符串短的放在前面，字符串长的放在后面
        int index = 0;
        for(List<String> list : wordsLengths){
            for(String temp : list){
                array[index] = temp;
                index++;
            }
        }

        //4. 从最后一位开始依次进行多次桶排序
        int startIndex = length;
        for(int i = maxStrLen - 1; i >= 0; i--){
            startIndex = startIndex - wordsLengths[i + 1].size();

            //4.1 扫描待排序数组，然后将元素放入到桶中
            for(int j = startIndex; j < length; j++){
                buckets[array[j].charAt(i)].add(array[j]);
            }

            //4.2 每次桶排序结束后，从桶中取值
            index = startIndex;
            for(List<String> list : buckets){
                for(String temp : list){
                    array[index] = temp;
                    index++;
                }

                //4.3 清空List
                list.clear();
            }
        }

        return array;
    }

    /**
     * 基数排序（使用 ArrayList 辅助排序不定长字符串数组，且以位数为基准进行排序）
     * <p><b>时间复杂度：</b>O(p(N + b))，其中p是趟数，N是待排序元素个数，b是桶</p>
     * @author zifangsky
     * @date 2019/1/15 16:37
     * @since 1.0.0
     * @param array 待排序数组
     */
    public static String[] sortStr4(String[] array){
        if(array == null || array.length < 1){
            throw new IllegalArgumentException("Illegal initial array");
        }

        //获取数组中的字符串的最大位数
        int maxStrLen = findMaxDigit(array);
        int length = array.length;

        //1. 定义一个 length 长的数组，并初始化
        List<String>[] buckets = new ArrayList[BUCKETS];
        //2. 按照输入的字符串的不同长度，将它们分割到不同的 List 中
        List<String>[] wordsLengths = new ArrayList[maxStrLen + 1];

        for(int i = 0; i < BUCKETS; i++){
            buckets[i] = new ArrayList<>();
        }
        for(int i = 0; i < wordsLengths.length; i++){
            wordsLengths[i] = new ArrayList<>();
        }
        for(String temp : array){
            wordsLengths[temp.length()].add(temp);
        }

        //3. 重新排序原数组，将字符串短的放在前面，字符串长的放在后面
        int index = 0;
        for(List<String> list : wordsLengths){
            for(String temp : list){
                array[index] = temp;
                index++;
            }
        }

        //4. 将相同位数的字符串分别进行多次桶排序
        int startIndex = length,end;
        for(int strLen = maxStrLen; strLen > 0; strLen--){
            end = startIndex;
            startIndex = startIndex - wordsLengths[strLen].size();

            //4.1 排序位数相同的那些字符串
            for(int i = strLen - 1; i >= 0; i--){
                //4.1.1 扫描待排序数组，然后将元素放入到桶中
                for(int j = startIndex; j < end; j++){
                    buckets[array[j].charAt(i)].add(array[j]);
                }

                //4.1.2 每次桶排序结束后，从桶中取值
                index = startIndex;
                for(List<String> list : buckets){
                    for(String temp : list){
                        array[index] = temp;
                        index++;
                    }

                    //4.1.3 清空List
                    list.clear();
                }
            }
        }

        return array;
    }



    /**
     * 查找数组的最大位数
     */
    private static int findMaxDigit(String[] array){
        int result = array[0].length();

        for(String temp : array){
            if(temp.length() > result){
                result = temp.length();
            }
        }

        return result;
    }

}
